{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stepping Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSteppingNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #步进数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 <code>1</code>，那么这个数就是一个「步进数」。</p>\n",
    "\n",
    "<p>例如，<code>321</code>&nbsp;是一个步进数，而&nbsp;<code>421</code>&nbsp;不是。</p>\n",
    "\n",
    "<p>给你两个整数，<code>low</code>&nbsp;和&nbsp;<code>high</code>，请你找出在&nbsp;<code>[low, high]</code>&nbsp;范围内的所有步进数，并返回&nbsp;<strong>排序后</strong> 的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>low = 0, high = 21\n",
    "<strong>输出：</strong>[0,1,2,3,4,5,6,7,8,9,10,12,21]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= low &lt;= high &lt;= 2 * 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stepping-numbers](https://leetcode.cn/problems/stepping-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stepping-numbers](https://leetcode.cn/problems/stepping-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['0\\n21', '10\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ceil = 2*10**9\n",
    "pre = list(range(10))\n",
    "ans = [0]\n",
    "\n",
    "def dfs():\n",
    "    global num\n",
    "    if num > ceil:\n",
    "        return \n",
    "    ans.append(num)\n",
    "    last = num % 10\n",
    "    for x in [last-1, last+1]:\n",
    "        if 0 <= x <= 9:\n",
    "            num = num*10 + x\n",
    "            dfs()\n",
    "            num //= 10\n",
    "    return \n",
    "\n",
    "for i in range(1, 10):\n",
    "    num = i\n",
    "    dfs()\n",
    "\n",
    "ans.sort()\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        i, j = bisect.bisect_left(ans, low), bisect.bisect_right(ans, high)\n",
    "        return ans[i:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        heap = [i for i in range(1, 10)]\n",
    "        while heap[0] <= high:\n",
    "            cur = heapq.heappop(heap)\n",
    "            if cur >= low:  ans.append(cur)\n",
    "            if cur % 10 > 0:    heapq.heappush(heap, cur * 10 + cur % 10 - 1)\n",
    "            if cur % 10 < 9:    heapq.heappush(heap, cur * 10 + cur % 10 + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ceil = 2*10**9\n",
    "pre = list(range(10))\n",
    "ans = set()\n",
    "\n",
    "def dfs():\n",
    "    global num\n",
    "    if num > ceil:\n",
    "        return \n",
    "    ans.add(num)\n",
    "    last = num % 10\n",
    "    for x in [last-1, last+1]:\n",
    "        if 0 <= x <= 9:\n",
    "            num = num*10 + x\n",
    "            dfs()\n",
    "            num //= 10\n",
    "    return \n",
    "\n",
    "for i in range(10):\n",
    "    num = i\n",
    "    dfs()\n",
    "\n",
    "ans = sorted(list(ans))\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        i, j = bisect.bisect_right(ans, high), bisect.bisect_left(ans, low)\n",
    "        return ans[j:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        stack=collections.deque()\n",
    "        for i in range(1,10):\n",
    "            stack.append(i)\n",
    "        vis=set()\n",
    "        vis.add(0)\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            if cur in vis:\n",
    "                continue \n",
    "            vis.add(cur)\n",
    "            j=cur%10+1\n",
    "            if j<10:\n",
    "                new=cur*10+j\n",
    "                if new not in vis and new<=high:\n",
    "                    stack.append(new)\n",
    "            k=cur%10-1\n",
    "            if k>=0:\n",
    "                new=cur*10+k\n",
    "                if new not in vis and new<=high:\n",
    "                    stack.append(new)\n",
    "     \n",
    "        ans=[]\n",
    "        for i in vis:\n",
    "            if i>=low and i<=high:\n",
    "                ans.append(i)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        heap = [i for i in range(1, 10)]\n",
    "        while heap[0] <= high:\n",
    "            cur = heapq.heappop(heap)\n",
    "            if cur >= low:  ans.append(cur)\n",
    "            if cur % 10 > 0:    heapq.heappush(heap, cur * 10 + cur % 10 - 1)\n",
    "            if cur % 10 < 9:    heapq.heappush(heap, cur * 10 + cur % 10 + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        result, q = [], deque([*range(1, 10)])\n",
    "        not low and result.append(0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            low <= x <= high and result.append(x)\n",
    "            x, m = x * 10, x % 10\n",
    "            m and x + m - 1 <= high and q.append(x + m - 1)\n",
    "            m < 9 and x + m - 1 <= high and q.append(x + m + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]: \n",
    "        ans = [] \n",
    "        vis = set()\n",
    "        Q = deque()\n",
    "        for i in range(1,10):\n",
    "            Q.append(i)\n",
    "            vis.add(i)\n",
    "        while Q:\n",
    "            x = Q.popleft() \n",
    "            if low <= x <= high:\n",
    "                ans.append(x) \n",
    "            if x > high:\n",
    "                continue \n",
    "            if x % 10 > 0:\n",
    "                nx = x * 10 + (x%10 - 1) \n",
    "                if nx <= high:\n",
    "                    Q.append(nx) \n",
    "            if x % 10 < 9:\n",
    "                nx = x * 10 + (x%10 + 1) \n",
    "                if nx <= high:\n",
    "                    Q.append(nx) \n",
    "        if low == 0:\n",
    "            ans.insert(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        Q = deque([1, 2,3,4,5,6,7,8,9])\n",
    "        ans = [] \n",
    "        while Q:\n",
    "            x = Q.popleft() \n",
    "            if low <= x <= high:\n",
    "                ans.append(x) \n",
    "            for y in [x % 10 - 1, x % 10 + 1]:\n",
    "                if 0<=y<10:\n",
    "                    nxt = x * 10 + y \n",
    "                    if nxt <= high:\n",
    "                        Q.append(nxt)\n",
    "        if low == 0:\n",
    "            ans.insert(0, 0) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        res = []\n",
    "        if low == 0:\n",
    "            res.append(0)\n",
    "        queue = [x for x in range(1, 10)]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur > high:\n",
    "                return res \n",
    "            if low <= cur:\n",
    "                res.append(cur)\n",
    "            last_bit = cur % 10\n",
    "            if last_bit > 0:\n",
    "                queue.append(cur * 10 + (last_bit - 1))\n",
    "            if last_bit < 9:\n",
    "                queue.append(cur * 10 + (last_bit + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        heap = [i for i in range(1, 10)]\n",
    "        while heap[0] <= high:\n",
    "            cur = heapq.heappop(heap)\n",
    "            if cur >= low:  ans.append(cur)\n",
    "            if cur % 10 > 0:    heapq.heappush(heap, cur * 10 + cur % 10 - 1)\n",
    "            if cur % 10 < 9:    heapq.heappush(heap, cur * 10 + cur % 10 + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:\n",
    "            result = [0]\n",
    "        else:\n",
    "            result = []\n",
    "        dq = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
    "\n",
    "        def bfs():\n",
    "            depth = 0\n",
    "            while dq:\n",
    "                depth += 1\n",
    "                for _ in range(len(dq)):\n",
    "                    tmp = dq.popleft()\n",
    "                    if tmp > high:\n",
    "                        continue\n",
    "                    if low <= tmp <= high:\n",
    "                        result.append(tmp)\n",
    "                    last_num = tmp % 10\n",
    "                    if last_num > 0:\n",
    "                        num1 = 10*tmp + last_num - 1\n",
    "                        dq.append(num1)\n",
    "                    if last_num < 9:\n",
    "                        num1 = 10*tmp + last_num + 1\n",
    "                        dq.append(num1)\n",
    "\n",
    "        bfs()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        # BFS approach\n",
    "        queue = deque(list(range(10))) # initialize queue with numbers from 0 to 9\n",
    "        res = []\n",
    "        \n",
    "        while queue:\n",
    "            num = queue.popleft()\n",
    "            \n",
    "            # If current number is in range, add it to the result list\n",
    "            if low <= num <= high:\n",
    "                res.append(num)\n",
    "            \n",
    "            # If current number is 0 or greater than high, skip the generation of next numbers\n",
    "            if num == 0 or num > high:\n",
    "                continue\n",
    "            \n",
    "            # Generate the next stepping number\n",
    "            last_digit = num % 10\n",
    "            # Append last_digit - 1\n",
    "            if last_digit > 0:\n",
    "                next_num = num * 10 + last_digit - 1\n",
    "                if next_num <= high:\n",
    "                    queue.append(next_num)\n",
    "            # Append last_digit + 1\n",
    "            if last_digit < 9:\n",
    "                next_num = num * 10 + last_digit + 1\n",
    "                if next_num <= high:\n",
    "                    queue.append(next_num)\n",
    "        \n",
    "        return sorted(filter(lambda x: x >= low, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:\n",
    "            result = set([0])\n",
    "        else:\n",
    "            result = set()\n",
    "        dq = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
    "\n",
    "        def bfs():\n",
    "            depth = 0\n",
    "            while dq:\n",
    "                depth += 1\n",
    "                for _ in range(len(dq)):\n",
    "                    tmp = dq.popleft()\n",
    "                    if tmp > high:\n",
    "                        continue\n",
    "                    if low <= tmp <= high:\n",
    "                        result.add(tmp)\n",
    "                    last_num = tmp % 10\n",
    "                    if last_num == 0:\n",
    "                        num1 = 10*tmp + last_num + 1\n",
    "                        if num1 not in result:\n",
    "                            dq.append(num1)\n",
    "                    elif last_num == 9:\n",
    "                        num1 = 10*tmp + last_num - 1\n",
    "                        if num1 not in result:\n",
    "                            dq.append(num1)\n",
    "                    else:\n",
    "                        num1 = 10*tmp + last_num + 1\n",
    "                        if num1 not in result:\n",
    "                            dq.append(num1)\n",
    "                        num2 = 10*tmp + last_num - 1\n",
    "                        if num1 not in result:\n",
    "                            dq.append(num2)\n",
    "\n",
    "        bfs()\n",
    "        result = list(result)\n",
    "        result.sort()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]: \n",
    "        ans = [] \n",
    "        vis = set()\n",
    "        Q = deque()\n",
    "        for i in range(10):\n",
    "            Q.append(i)\n",
    "            vis.add(i)\n",
    "        while Q:\n",
    "            x = Q.popleft() \n",
    "            if low <= x <= high:\n",
    "                ans.append(x) \n",
    "            if x > high:\n",
    "                continue \n",
    "            if x % 10 < 9:\n",
    "                nx = x * 10 + (x%10 + 1) \n",
    "                if nx not in vis:\n",
    "                    vis.add(nx) \n",
    "                    Q.append(nx) \n",
    "            if x % 10 > 0:\n",
    "                nx = x * 10 + (x%10 - 1) \n",
    "                if nx not in vis:\n",
    "                    vis.add(nx) \n",
    "                    Q.append(nx)\n",
    "        return sorted(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        temp = []\n",
    "        def dfs(i):\n",
    "            temp.append(str(i))\n",
    "            num = int(\"\".join(temp))\n",
    "            if num > high:\n",
    "                temp.pop()\n",
    "                return\n",
    "            elif num >= low:\n",
    "                ans.append(num)\n",
    "            \n",
    "            if i > 0:   dfs(i-1)\n",
    "            if i < 9:   dfs(i+1)\n",
    "            temp.pop()\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            dfs(i)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        temp = []\n",
    "        def dfs(i):\n",
    "            temp.append(str(i))\n",
    "            num = int(\"\".join(temp))\n",
    "            if num > high:\n",
    "                temp.pop()\n",
    "                return\n",
    "            elif num >= low:\n",
    "                ans.append(num)\n",
    "            \n",
    "            if i > 0:   dfs(i-1)\n",
    "            if i < 9:   dfs(i+1)\n",
    "            temp.pop()\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            dfs(i)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        temp = []\n",
    "        def dfs(i):\n",
    "            temp.append(str(i))\n",
    "            num = int(\"\".join(temp))\n",
    "            if num > high:\n",
    "                temp.pop()\n",
    "                return\n",
    "            elif num >= low:\n",
    "                ans.append(num)\n",
    "            \n",
    "            if i > 0:   dfs(i-1)\n",
    "            if i < 9:   dfs(i+1)\n",
    "            temp.pop()\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            dfs(i)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        if low == 0:    ans = [0]\n",
    "        else:   ans = []\n",
    "        temp = []\n",
    "        def dfs(i):\n",
    "            temp.append(str(i))\n",
    "            num = int(\"\".join(temp))\n",
    "            if num > high:\n",
    "                temp.pop()\n",
    "                return\n",
    "            elif num >= low:\n",
    "                ans.append(num)\n",
    "            \n",
    "            if i > 0:   dfs(i-1)\n",
    "            if i < 9:   dfs(i+1)\n",
    "            temp.pop()\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            dfs(i)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        ls=[]\n",
    "        def dfs(now,last):\n",
    "            #print(now,last)\n",
    "            if now>high:\n",
    "                return \n",
    "            if now>=low:\n",
    "                ls.append(now)\n",
    "            if last>0:\n",
    "                dfs(now*10+last-1,last-1)\n",
    "            if last<9:\n",
    "                dfs(now*10+last+1,last+1)\n",
    "        for i in range(1,10):\n",
    "            dfs(i,i)\n",
    "        if low==0:\n",
    "            ls.append(0)\n",
    "        ls.sort()\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSteppingNumbers(self, low: int, high: int) -> List[int]:\n",
    "        ans = []\n",
    "        if low == 0:\n",
    "            ans.append(0)\n",
    "        def dfs(pre, cur):\n",
    "            if cur > high:\n",
    "                return\n",
    "            if low <= cur <= high:\n",
    "                ans.append(cur)\n",
    "            if pre is None:\n",
    "                for i in range(1, 10):\n",
    "                    dfs(i, i)\n",
    "            else:\n",
    "                if -1 < pre + 1 < 10:\n",
    "                    dfs(pre + 1, cur * 10 + (pre + 1))\n",
    "                if -1 < pre - 1 < 10:\n",
    "                    dfs(pre - 1, cur * 10 + (pre - 1))\n",
    "            # return 0\n",
    "        dfs(None, 0)\n",
    "        return list(sorted(set(ans)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
